package LeetCode;

public class LC_028_ImplementstrStr {
    public static void main(String[] args) {
        String s = "12345";
        String m = "";
        int i = strStr_2(s, m);
        System.out.println(i);
    }

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    private static int strStr_2(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        if (haystack == null || haystack.length() < needle.length())
            return -1;
        return getIndexOf(haystack, needle);
    }


    private static int getIndexOf(String s, String m) {
        if (s == null || m == null || s.length() < m.length())
            return -1;

        char[] sa = s.toCharArray();
        char[] ma = m.toCharArray();
        int i = 0, j = 0;

        int[] next = getNextArray(m);

        while (i < sa.length && j < ma.length) {
            if (sa[i] == ma[j]) {
                i++;
                j++;
            } else if (next[j] == -1)
                i++;
            else
                j = next[j];
        }

        return j == m.length() ? i - j : -1;
    }

    private static int[] getNextArray(String m) {
        if (m.length() == 1)
            return new int[]{1};

        char[] ma = m.toCharArray();
        int[] next = new int[m.length()];
        next[0] = -1;
        next[1] = 0;
        int cn = 0, pos = 1;

        while (pos < next.length - 1) {
            if (ma[cn] == ma[pos])
                next[++pos] = ++cn;
            else if (cn > 0)
                cn = next[cn];
            else
                next[++pos] = 0;
        }

        return next;
    }
}
